//给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。 
//
// 你可以假设除了数字 0 之外，这两个数字都不会以零开头。 
//
// 
//
// 示例1： 
//
// 
//
// 
//输入：l1 = [7,2,4,3], l2 = [5,6,4]
//输出：[7,8,0,7]
// 
//
// 示例2： 
//
// 
//输入：l1 = [2,4,3], l2 = [5,6,4]
//输出：[8,0,7]
// 
//
// 示例3： 
//
// 
//输入：l1 = [0], l2 = [0]
//输出：[0]
// 
//
// 
//
// 提示： 
//
// 
// 链表的长度范围为 [1, 100] 
// 0 <= node.val <= 9 
// 输入数据保证链表代表的数字无前导 0 
// 
//
// 
//
// 进阶：如果输入链表不能修改该如何处理？换句话说，不能对列表中的节点进行翻转。 
// Related Topics 栈 链表 数学 
// 👍 413 👎 0

  
package com.zwy.leetcode.editor.cn;

import com.zwy.leetcode.ListNode;

import java.util.Stack;

public class AddTwoNumbersIi{
    public static void main(String[] args) {
        Solution solution = new AddTwoNumbersIi().new Solution();
//        l1 = [7,2,4,3], l2 = [5,6,4]
        ListNode l1=new ListNode(1);
        ListNode l2=new ListNode(9,new ListNode(9));
        solution.addTwoNumbers(l1,l2);
      }
      //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer>stack1=new Stack<>();
        Stack<Integer>stack2=new Stack<>();
        Stack<Integer>resStack=new Stack<>();
        ListNode res=new ListNode();
        while(l1!=null||l2!=null){
            if(l1!=null){
                stack1.push(l1.val);
                l1=l1.next;
            }
            if(l2!=null){
                stack2.push(l2.val);
                l2=l2.next;
            }
        }
        int len=Math.max(stack1.size(),stack2.size());
        int num1=0;
        int num2=0;
        int t=0;
        boolean flag=false;
        for (int i = 0; i < len; i++) {
            num1=0;
            num2=0;
            t=0;
            if(!stack1.isEmpty()){
                num1=stack1.pop();
            }
            if(!stack2.isEmpty()){
                num2=stack2.pop();
            }
            if(flag)t++;
            if(num1+num2+t>=10){
                flag=true;
                t+=num1+num2-10;
            }
            else {
                flag=false;
                t+=num1+num2;
            }
            resStack.push(t);
        }
        if(flag)resStack.push(1);
        len=resStack.size();
        ListNode p=null;
        res=new ListNode(resStack.peek());
        p=res;
        for (int i = 0; i < len; i++) {
            p.next=new ListNode(resStack.pop());
            p=p.next;
        }
        return res.next;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}